package graph;

import java.util.Arrays;

/**
 * 并查集
 */
public class UnionFindSet {
    private int[] elem;
    public UnionFindSet(int n){
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }

    /**
     * 查找根结点
     * @return
     */
    public int findRoot(int x){
        while(elem[x] >= 0){
            x = elem[x];
        }
        return x;

    }

    /**
     * 判断两个节点是否是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1,int x2){
        int root1 = findRoot(x1);
        int root2 = findRoot(x2);
        return root1 == root2;
    }

    /**
     * 合并两个集合
     *
     * @param x1
     * @param x2
     */
    public void union(int x1, int x2){

        int root1 = findRoot(x1);
        int root2 = findRoot(x2);
        if(root1 == root2){
            return;
        }
        elem[root1] = elem[root1] + elem[root2];
        elem[root2] = root1;



    }

    public int getCount(){
        int count = 0;
        for ( int x : elem ) {
            if(x < 0){
                count++;
            }
        }
        return  count;
    }
    public void print() {
        for (int x : elem) {
            System.out.print(x+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        System.out.println("合并：0和6：");
        unionFindSet.union(0,6);
        System.out.println("合并：0和7：");
        unionFindSet.union(0,7);
        System.out.println("合并：0和8：");
        unionFindSet.union(0,8);

        System.out.println("合并：1和4：");
        unionFindSet.union(1,4);
        System.out.println("合并：1和9：");
        unionFindSet.union(1,9);
        System.out.println("合并：2和3：");
        unionFindSet.union(2,3);

        System.out.println("合并：2和5：");
        unionFindSet.union(2,5);

        unionFindSet.print();

        System.out.println("合并：8和1：");
        unionFindSet.union(8,1);

        unionFindSet.print();

        System.out.println("查找是不是同一个集合");
        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
        System.out.println(unionFindSet.isSameUnionFindSet(8, 2));
    }



}
